Structures
using System;
namespace algorithms.structures
{
// ----- Binary Heap PQ (Priority Queue) -----------------------------------
//
// A heap data structure that takes the form of a binary tree and
// implements a priority queue
//
// O(n) preprocessing
// O(logn) insert/extract min
//
// BinaryHeapPQ<T> where T : IComparable
//
// BinaryHeapPQ()
// BinaryHeapPQ(int capacity)
// BinaryHeapPQ(T[] a)
// int Count
// T Min
// void Insert(T x)
// T ExtractMin()
// -------------------------------------------------------------------------
public class BinaryHeapPQ<T> where T : IComparable
{
int n = 0;
T[] que = null;
public BinaryHeapPQ() : this(1) { }
public BinaryHeapPQ(int capacity)
{
que = new T[capacity + 1];
n = 0;
}
public BinaryHeapPQ(T[] a)
{
n = a.Length;
que = new T[n + 1];
for (int i = 0; i < n; i++) que[i + 1] = a[i];
for (int i = n / 2; i >= 1; i--) Sink(i);
}
public int Count { get { return n; } }
public T Min { get { return que[1]; } }
public void Insert(T x)
{
if (n == que.Length - 1) Resize(que.Length * 2);
que[++n] = x;
Swim(n);
}
public T ExtractMin()
{
Swap(1, n);
T min = que[n--];
Sink(1);
que[n + 1] = default(T);
return min;
}
void Swim(int k)
{
while (k > 1 && que[k/2].CompareTo(que[k]) > 0)
{
Swap(k, k / 2);
k = k / 2;
}
}
void Sink(int k)
{
while (2 * k <= n)
{
int j = 2 * k;
if (j < n && que[j].CompareTo(que[j+1]) > 0) j++;
if (que[k].CompareTo(que[j]) <= 0) break;
Swap(k, j);
k = j;
}
}
void Resize(int capacity)
{
T[] temp = new T[capacity + 1];
for (int i = 1; i <= n; i++) temp[i] = que[i];
que = temp;
}
void Swap(int i, int j)
{
T temp = que[i];
que[i] = que[j];
que[j] = temp;
}
}
// -------------------------------------------------------------------------
}
using System;
namespace algorithms.structures
{
public static class BinaryIndexedTree
{
// ----- Binary Indexed Tree (Fenwick Tree) ----------------------------
//
// A data structure that can efficiently update elements and calculate
// prefix sums in a table of numbers
//
// O(nlogn) create
// O(logn) update / get prefix sum
//
// int[] CreateFenwick(int[] a)
// void UpdateFenwick(int[] ft, int v, int ix)
// int SumFenwick(int[] ft, int ix)
// ---------------------------------------------------------------------
// int[,] CreateFenwick(int[,] a)
// void UpdateFenwick(int[,] ft, int v, int ix, int jx)
// int SumFenwick(int[,] ft, int ix, int jx)
// ---------------------------------------------------------------------
// int[] CreateFenwick(int[] a, Func<int, int, int> func)
// void UpdateFenwick(int[] ft, int v, int ix, Func<int, int, int> func)
// int SumFenwick(int[] ft, int ix, Func<int, int, int> func)
// ---------------------------------------------------------------------
public static int[] CreateFenwick(int[] a)
{
int[] ft = new int[a.Length + 1];
for (int i = 1; i <= a.Length; i++) UpdateFenwick(ft, a[i - 1], i);
return ft;
}
public static void UpdateFenwick(int[] ft, int v, int ix)
{
while (ix < ft.Length)
{
ft[ix] += v;
ix = ix + (ix & -ix);
}
}
public static int SumFenwick(int[] ft, int ix)
{
ix++;
int sum = 0;
while (ix > 0)
{
sum += ft[ix];
ix = ix - (ix & -ix);
}
return sum;
}
// ---------------------------------------------------------------------
public static int[,] CreateFenwick(int[,] a)
{
int[,] ft = new int[a.GetLength(0) + 1, a.GetLength(1) + 1];
for (int i = 1; i <= a.GetLength(0); i++)
for (int j = 1; j <= a.GetLength(1); j++)
UpdateFenwick(ft, a[i - 1, j - 1], i, j);
return ft;
}
public static void UpdateFenwick(int[,] ft, int v, int ix, int jx)
{
while (ix < ft.GetLength(0))
{
while (jx < ft.GetLength(1))
{
ft[ix, jx] += v;
jx = jx + (jx & -jx);
}
ix = ix + (ix & -ix);
}
}
public static int SumFenwick(int[,] ft, int ix, int jx)
{
ix++;
jx++;
int sum = 0;
while (ix > 0)
{
while (jx > 0)
{
sum += ft[ix, jx];
jx = jx - (jx & -jx);
}
ix = ix - (ix & -ix);
}
return sum;
}
// ---------------------------------------------------------------------
public static int[] CreateFenwick(int[] a, Func<int, int, int> func)
{
int[] ft = new int[a.Length + 1];
for (int i = 1; i <= a.Length; i++) UpdateFenwick(ft, a[i - 1], i, func);
return ft;
}
public static void UpdateFenwick(int[] ft, int v, int ix, Func<int, int, int> func)
{
while (ix < ft.Length)
{
ft[ix] = func(ft[ix], v);
ix = ix + (ix & -ix);
}
}
public static int SumFenwick(int[] ft, int ix, Func<int, int, int> func)
{
ix++;
int sum = 0;
while (ix > 0)
{
sum = func(sum, ft[ix]);
ix = ix - (ix & -ix);
}
return sum;
}
// ---------------------------------------------------------------------
}
}
namespace algorithms.structures
{
// ----- Disjoint Sets -----------------------------------------------------
// DisjointSets(int count)
// void MakeSet(int x)
// int FindSet(int x)
// void Union(int x, int y)
// -------------------------------------------------------------------------
public class DisjointSets
{
int[] parent = null;
int[] rank = null;
public DisjointSets(int count)
{
parent = new int[count];
rank = new int[count];
for (int i = 0; i < count; i++)
{
parent[i] = i;
rank[i] = 0;
}
}
public void MakeSet(int x)
{
parent[x] = x;
rank[x] = 0;
}
public int FindSet(int x)
{
if (parent[x] != x) parent[x] = FindSet(parent[x]);
return parent[x];
}
public void Union(int x, int y)
{
int xroot = FindSet(x);
int yroot = FindSet(y);
if (rank[xroot] < rank[yroot]) parent[xroot] = yroot;
else if (rank[xroot] > rank[yroot]) parent[yroot] = xroot;
else
{
parent[yroot] = xroot;
rank[xroot]++;
}
}
}
// -------------------------------------------------------------------------
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace algorithms.structures
{
// ----- Index Binary Heap PQ (Priority Queue) -----------------------------
//
// http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/IndexMinPQ.java.html
//
// Minimum-oriented indexed PQ implementation using a binary heap
//
// O(n) preprocessing
// O(logn) insert/extract min
//
// IndexBinaryHeapPQ<T> where T : IComparable
//
// IndexBinaryHeapPQ(int maxN)
// int Count
// bool Contains(int ix)
// int Count
// T KeyOf(int ix)
// int MinIndex
// T MinKey
// bool Insert(int ix, T key)
// bool Change(int ix, T key)
// bool Increase(int ix, T key)
// bool Decrease(int ix, T key)
// bool Remove(int ix)
// int ExtractMin()
// -------------------------------------------------------------------------
public class IndexBinaryHeapPQ<T> where T : IComparable
{
int maxN = 0;
int n = 0;
int[] pq = null;
int[] qp = null;
T[] keys = null;
public IndexBinaryHeapPQ(int maxN)
{
this.maxN = maxN;
n = 0;
keys = new T[maxN + 1];
pq = new int[maxN + 1];
qp = new int[maxN + 1];
for (int i = 0; i <= maxN; i++) qp[i] = -1;
}
public int Count { get { return n; } }
public bool Contains(int ix) { return qp[ix] != -1; }
public T KeyOf(int ix) { return keys[ix]; }
public int MinIndex { get { return pq[1]; } }
public T MinKey { get { return keys[pq[1]]; } }
public bool Insert(int ix, T key)
{
if (Contains(ix)) return false;
n++;
qp[ix] = n;
pq[n] = ix;
keys[ix] = key;
Swim(n);
return true;
}
public bool Change(int ix, T key)
{
if (!Contains(ix)) return false;
keys[ix] = key;
Swim(qp[ix]);
Sink(qp[ix]);
return true;
}
public bool Increase(int ix, T key)
{
if (!Contains(ix)) return false;
if (keys[ix].CompareTo(key) >= 0) return false;
keys[ix] = key;
Sink(qp[ix]);
return true;
}
public bool Decrease(int ix, T key)
{
if (!Contains(ix)) return false;
if (keys[ix].CompareTo(key) <= 0) return false;
keys[ix] = key;
Swim(qp[ix]);
return true;
}
public bool Remove(int ix)
{
if (!Contains(ix)) return false;
int index = qp[ix];
Swap(index, n--);
Swim(index);
Sink(index);
keys[ix] = default(T);
qp[ix] = -1;
return true;
}
public int ExtractMin()
{
int min = pq[1];
Swap(1, n--);
Sink(1);
qp[min] = -1;
keys[min] = default(T);
pq[n + 1] = -1;
return min;
}
void Swim(int k)
{
while (k > 1 && keys[pq[k / 2]].CompareTo(keys[pq[k]]) > 0)
{
Swap(k, k / 2);
k = k / 2;
}
}
void Sink(int k)
{
while (2 * k <= n)
{
int j = 2 * k;
if (j < n && keys[pq[j]].CompareTo(keys[pq[j + 1]]) > 0) j++;
if (keys[pq[k]].CompareTo(keys[pq[j]]) <= 0) break;
Swap(k, j);
k = j;
}
}
void Swap(int i, int j)
{
int swap = pq[i];
pq[i] = pq[j];
pq[j] = swap;
qp[pq[i]] = i;
qp[pq[j]] = j;
}
}
// -------------------------------------------------------------------------
}
namespace algorithms.structures
{
// ----- Linked List Array ------------------------------------------------------
//
// int M
// int Current
// int Count
// LinkedListArray(int m)
// void First()
// void Next()
// bool Add()
// bool Remove()
// -------------------------------------------------------------------------
public class LinkedListArray
{
int[] list = null;
int first = 0;
int prev = 0;
int[] heap = null;
int ixh = 0;
int len = 0;
public int M { get; private set; }
public int Current { get; private set; }
public int Count { get { return M - len; } }
public LinkedListArray(int m)
{
M = m;
list = new int[M];
heap = new int[M];
for (int i = 0; i < M; i++) heap[i] = i;
ixh = 0;
len = M;
first = -1;
prev = -1;
Current = -1;
}
public void First()
{
prev = first;
Current = first;
}
public void Next()
{
if (Current >= 0)
{
Current = list[Current];
if (list[first] != Current) prev = list[prev];
}
}
public bool Add()
{
if (len == 0) return false;
int nix = heap[ixh++];
ixh %= M;
len--;
if (Current >= 0)
{
list[nix] = list[Current];
list[Current] = nix;
}
else
{
list[nix] = first;
first = nix;
}
prev = Current;
Current = nix;
return true;
}
public bool Remove()
{
if (Current < 0) return false;
int ix = list[Current];
if (Current == first)
{
first = list[ix];
Current = first;
prev = first;
}
else
{
list[prev] = list[Current];
Current = list[Current];
}
heap[(ixh + len) % M] = ix;
len++;
return true;
}
}
// -------------------------------------------------------------------------
}
using System;
namespace algorithms.structures
{
// ----- Segment Tree ------------------------------------------------------
//
// A structure for efficient search of cummulative data.
// Range Minimum (Maximum) Query
// Range Sum (Multiplication) Query
//
// O(nlogn) preprocessing
// O(logn) a single query
//
// LazyPropagation - for range updates, which means when you perform
// update operations over a range, the update process affects
// the least nodes as possible so that the bigger the range you want
// to update the less time it consumes to update it.
// Eventually those changes will be propagated to the children and
// the whole array will be up to date.
//
// http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/SegmentTree.java.html
//
// struct Node {
// public int Sum { get; set; }
// public int Min { get; set; }
// public int? PendingValue { get; set; } //Lazily propagated value
// ...
// }
//
// SegmentTree(int[] array)
// int Size
// int RSumQ(int from, int to)
// int RMinQ(int from, int to)
// void Update(int from, int to, int value)
// -------------------------------------------------------------------------
public class SegmentTree
{
struct Node
{
public long Sum { get; set; }
public int Min { get; set; }
public int? PendingValue { get; set; } //Lazily propagated value
public int From { get; set; }
public int To { get; set; }
public int Size() { return To - From + 1; }
}
Node[] heap = null;
int[] array = null;
int size = 0;
public SegmentTree(int[] array)
{
this.array = array;
//The max size of this array is about 2 * 2 ^ log2(n) + 1
size = (int)(2 * Math.Pow(2.0, (int)((Math.Log(array.Length) / Math.Log(2.0)) + 1)));
heap = new Node[size];
Build(1, 0, array.Length);
}
public int Size { get { return array.Length; } }
void Build(int v, int from, int size)
{
heap[v] = new Node();
heap[v].From = from;
heap[v].To = from + size - 1;
if (size == 1)
{
heap[v].Sum = array[from];
heap[v].Min = array[from];
}
else
{
Build(2 * v, from, size / 2);
Build(2 * v + 1, from + size / 2, size - size / 2);
heap[v].Sum = heap[2 * v].Sum + heap[2 * v + 1].Sum;
heap[v].Min = Math.Min(heap[2 * v].Min, heap[2 * v + 1].Min);
}
}
public long RSumQ(int from, int to)
{
return RSumQ(1, from, to);
}
long RSumQ(int v, int from, int to)
{
Node n = heap[v];
if (n.PendingValue != null && Contains(n.From, n.To, from, to))
{
return (to - from + 1) * (int)n.PendingValue;
}
if (Contains(from, to, n.From, n.To))
{
return heap[v].Sum;
}
if (Intersects(from, to, n.From, n.To))
{
Propagate(v);
long leftSum = RSumQ(2 * v, from, to);
long rightSum = RSumQ(2 * v + 1, from, to);
return leftSum + rightSum;
}
return 0;
}
public int RMinQ(int from, int to)
{
return RMinQ(1, from, to);
}
int RMinQ(int v, int from, int to)
{
Node n = heap[v];
if (n.PendingValue != null && Contains(n.From, n.To, from, to))
{
return (int)n.PendingValue;
}
if (Contains(from, to, n.From, n.To))
{
return heap[v].Min;
}
if (Intersects(from, to, n.From, n.To))
{
Propagate(v);
int leftMin = RMinQ(2 * v, from, to);
int rightMin = RMinQ(2 * v + 1, from, to);
return Math.Min(leftMin, rightMin);
}
return int.MaxValue;
}
public void Update(int from, int to, int value)
{
Update(1, from, to, value);
}
void Update(int v, int from, int to, int value)
{
Node n = heap[v];
if (Contains(from, to, n.From, n.To))
{
Change(n, value);
}
if (n.Size() == 1) return;
if (Intersects(from, to, n.From, n.To))
{
Propagate(v);
Update(2 * v, from, to, value);
Update(2 * v + 1, from, to, value);
n.Sum = heap[2 * v].Sum + heap[2 * v + 1].Sum;
n.Min = Math.Min(heap[2 * v].Min, heap[2 * v + 1].Min);
}
}
void Propagate(int v)
{
Node n = heap[v];
if (n.PendingValue != null)
{
Change(heap[2 * v], (int)n.PendingValue);
Change(heap[2 * v + 1], (int)n.PendingValue);
n.PendingValue = null;
}
}
void Change(Node n, int value)
{
n.PendingValue = value;
n.Sum = (long)n.Size() * value;
n.Min = value;
array[n.From] = value;
}
bool Contains(int from1, int to1, int from2, int to2)
{
return from2 >= from1 && to2 <= to1;
}
bool Intersects(int from1, int to1, int from2, int to2)
{
return from1 <= from2 && to1 >= from2 // (.[..)..] or (.[...]..)
|| from1 >= from2 && from1 <= to2; // [.(..]..) or [..(..)..
}
}
}
using System;
namespace algorithms.structures
{
// ----- Segment Tree RMQ --------------------------------------------------
//
// A full binary tree to solve a Range Minimum Query problem
//
// O(n) preprocessing
// O(logn) a single query
//
// SegmentTreeRMQ<T> where T: IComparable
//
// SegmentTreeRMQ(int n, T maxValue)
// SegmentTreeRMQ(T[] a, T maxValue)
// void Update(int ix, T x)
//
// -- [left, right)
//
// T Min(int left, int right)
//
// -- [left
//
// int FirstLE(int left, T x)
//
// -- right]
//
// int LastLE(int right, T x)
// -------------------------------------------------------------------------
public class SegmentTreeRMQ<T> where T: IComparable
{
int n = 0;
int half = 0;
int size = 0;
T[] segmentTree = null;
T maxValue = default(T);
public SegmentTreeRMQ(int n, T maxValue)
{
this.n = n;
half = (int)next_highest_power_of_2((uint)n);
size = half * 2;
segmentTree = new T[size];
for (int i = 0; i < size; i++) segmentTree[i] = maxValue;
}
public SegmentTreeRMQ(T[] a, T maxValue)
{
n = a.Length;
half = (int)next_highest_power_of_2((uint)n);
size = half * 2;
segmentTree = new T[size];
this.maxValue = maxValue;
for (int i = 0; i < n; i++) segmentTree[half + i] = a[i];
for (int i = half + n; i < size; i++) segmentTree[i] = maxValue;
for (int i = half - 1; i >= 1; i--) Propagate(i);
}
public void Update(int ix, T x)
{
segmentTree[half + ix] = x;
for (int i = (half + ix) / 2; i >= 1; i /= 2) Propagate(i);
}
public T Min(int left, int right)
{
if (left >= right) return default(T);
T min = maxValue;
while (left != 0)
{
int f = left & -left;
if (left + f > right) break;
T v = segmentTree[(half + left) / f];
if (v.CompareTo(min) < 0) min = v;
left += f;
}
while (left < right)
{
int f = right & -right;
T v = segmentTree[(half + right) / f - 1];
if (v.CompareTo(min) < 0) min = v;
right -= f;
}
return min;
}
public int FirstLE(int left, T x)
{
int current = half + left;
while (true)
{
if (segmentTree[current].CompareTo(x) <= 0)
{
if (current >= half) return current - half;
current *= 2;
} else
{
current++;
if ((current & (current - 1)) == 0) return -1;
if (current % 2 == 0) current /= 2;
}
}
}
public int LastLE(int right, T x)
{
int current = half + right;
while (true)
{
if (segmentTree[current].CompareTo(x) <= 0)
{
if (current >= half) return current - half;
current = current * 2 + 1;
}
else
{
if ((current & (current - 1)) == 0) return -1;
current--;
if (current % 2 != 0) current /= 2;
}
}
}
void Propagate(int ix)
{
segmentTree[ix] = segmentTree[ix * 2].CompareTo(segmentTree[ix * 2 + 1]) < 0 ? segmentTree[ix * 2] : segmentTree[ix * 2 + 1];
}
static uint next_highest_power_of_2(uint v)
{
v--;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;
return v;
}
}
// -------------------------------------------------------------------------
}